package 题目集.数学;

import org.junit.Test;

/**
 * https://leetcode.cn/contest/weekly-contest-420/problems/minimum-division-operations-to-make-array-non-decreasing/
 */
public class demo06_使数组非递减的最少除法操作次数 {

    static int maxn = (int) (1e6 + 10);
    static int[] minPrime = new int[maxn];

    static {
        int m = (int) Math.sqrt(maxn);
        for (int i = 2; i <= m; i++) {
            if (minPrime[i] != 0) continue; /*合数*/
            for (int j = i + i; j < maxn; j += i) {
                if (minPrime[j] == 0) minPrime[j] = i;
            }
        }
    }

    /**
     * 脑筋急转弯+最小质因子.
     * 最大真因数=其除以最小质因子
     * 思路：从后向前遍历，如果当前数比后一个数小，则无需转化，比他大，则除最大真因数，如果除了还是大，则-1
     */
    public int minOperations(int[] nums) {
        /*上一个数*/
        int next = Integer.MAX_VALUE;
        int cnt = 0;
        for (int i = nums.length - 1; i >= 0; i--) {
            if (next < nums[i]) {
                nums[i] = minPrime[nums[i]] == 0 ? nums[i] : minPrime[nums[i]];
                cnt++;
                if (next < nums[i]) return -1;
            }
            next = nums[i];
        }
        return cnt;
    }

    @Test
    public void test() {
        int[] nums = {7,7,6};
        System.out.println(minOperations(nums));
    }
}
